package 剑指offer;

import java.util.Stack;

public class p30包含min函数的栈 {


    Stack<Integer> A=new Stack<>();
    Stack<Integer> B=new Stack<>();
    /** initialize your data structure here. */
    public p30包含min函数的栈() {

    }

    public void push(int x) {
        A.push(x);
        if (B.isEmpty() || B.peek()>=x){
            //两种情况下：当前元素X进入栈B
            //1.B为空栈   2.B栈的栈顶元素小于等于
            B.push(x);
        }
    }

    public void pop() {
        //当栈A弹出栈顶元素时，需要和栈B的栈顶元素进行比较，
        //当二者的栈顶元素相同时，则需要及时将栈B栈顶的元素也弹出，保证栈B的栈顶元素始终是栈A中已有的最小元素
        //当二者的栈顶元素不相同时，弹出栈A栈顶元素即可
        if (A.pop().equals(B.peek())){
            //==是指对内存地址进行比较 ， equals()是对字符串的内容进行比较
            //==指引用是否相同， equals()指的是值是否相同
            //==是判断两个变量或实例是不是指向同一个内存空间，equals是判断两个变量或实例所指向的内存空间的值是不是相同
            //所以不能用==!!!!!
            B.pop();
        }
    }

    public int top() {
        return A.peek();
    }

    public int min() {
        if (B.isEmpty()) {
            return -1;
        }else {
            return B.peek();
        }

    }

}

class MinStack {
    Stack<Integer> stack=new Stack<>(); //主栈
    Stack<Integer> findMin=new Stack<>(); //辅助栈，用来记录当前的最小元素


    /** initialize your data structure here. */
    public MinStack() {

    }

    public void push(int x) {
        stack.add(x);

        if (findMin.isEmpty() || findMin.peek()>=x) {
            //注意！ 相等也要进入辅助栈，否则影响弹出
            findMin.add(x);
        }
    }

    public void pop() {
        //弹出元素
        if (stack.isEmpty()) {
            return;
        }


        //使用 equals()比较两个 Integer类型
        if(stack.pop().equals(findMin.peek())) {
            findMin.pop();
        }


        //使用 == ，涉及 findMin.peek()的自动拆箱
        int pop=stack.pop();
        if(pop==findMin.peek()) {
            findMin.pop();
        }

        //或者
//        int pop=stack.pop();
//        int minpeek=findMin.peek();
//        if (pop==minpeek) {
//            findMin.pop();
//        }

    }

    public int top() {
        //查看首元素
        return stack.peek();
    }

    public int min() {
        return findMin.peek();
    }
}
